package leetcode.algorithm.linkedlist.simple.tree;

import leetcode.algorithm.TreeNode;

/**
 * 二叉树的最大深度
 *
 * @author jiangwz
 * @create 2019/11/7.
 */
public class Q104 {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3);
        TreeNode treeNode1 = new TreeNode(9);
        TreeNode treeNode2 = new TreeNode(20);
        TreeNode treeNode3 = new TreeNode(15);
        TreeNode treeNode4 = new TreeNode(7);

        treeNode.left = treeNode1;
        treeNode.right = treeNode2;

        treeNode2.left = treeNode3;
        treeNode2.right = treeNode4;
        System.out.println(new Q104().maxDepth(treeNode));
    }

    // 递归实现(效率较高)
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        return height(root);
    }

    public int height(TreeNode root){
        return Math.max(root.left == null?0:height(root.left), root.right == null?0:height(root.right))+1;
    }


//    执行用时 :
//            6 ms
//, 在所有 java 提交中击败了
//5.23%
//    的用户
//    内存消耗 :
//            37.7 MB
//, 在所有 java 提交中击败了
//40.63%
//    的用户
    // 队列实现
//    public int maxDepth(TreeNode root) {
//        if (root == null)
//            return 0;
//        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
//        if (root != null) {
//            queue.add(new Pair<>(root, 1));
//        }
//        int depth = 0;
//        while (!queue.isEmpty()) {
//            Pair<TreeNode, Integer> poll = queue.poll();
//            TreeNode node = poll.getKey();
//            Integer currDepth = poll.getValue();
//            if (node != null) {
//                depth = Math.max(depth, currDepth);
//                queue.add(new Pair<>(node.left, currDepth + 1));
//                queue.add(new Pair<>(node.right, currDepth + 1));
//            }
//        }
//        return depth;
//    }


}
